/**
 * 位图的实现
 */
#include <cds/bitmap.h>
#include <cds/string.h>

/**
 * @brief 映射了一个八位整形数第一个被置位的比特位，0映射为8。
 */
unsigned char get_byte_first_set_bit[256] = {
    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
};

/**
 * @brief 映射了一个八位整形数最后一个被置位的比特位，0映射为8。
 */
unsigned char get_byte_last_set_bit[256] = {
    8, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
};

struct bitmap *bitmap_init(struct bitmap *bm, void *buffer, size_t size)
{
    if (bm == NULL || buffer == NULL || size == 0) {
        return NULL;
    }
    if (size & (sizeof(long) - 1)) {
        /// 没有按 sizeof(long) 对齐。
        return NULL;
    }
    bm->map_size = size;
    bm->buffer = buffer;
    memset(buffer, 0, size);
    return bm;
}

void bitmap_clear_all(struct bitmap *bm)
{
    if (bitmap_is_initialized(bm)) {
        memset(bm->buffer, 0, bm->map_size);
    }
}

void bitmap_set_all(struct bitmap *bm)
{
    if (bitmap_is_initialized(bm)) {
        memset(bm->buffer, 0xff, bm->map_size);
    }
}

struct bitmap*
bitmap_copy(struct bitmap *new_bm, struct bitmap *old_bm, void *buffer)
{
    if (!bitmap_is_initialized(old_bm)) {
        return NULL;
    }
    if (new_bm == NULL || buffer == NULL) {
        return NULL;
    }

    new_bm->map_size = old_bm->map_size;
    new_bm->buffer = buffer;
    memcpy(buffer, old_bm->buffer, old_bm->map_size);

    return new_bm;
}

int bitmap_check_bit(struct bitmap *bm, long bit)
{
    if (bit >= bitmap_length(bm) && bit < 0) {
        return 0;
    }
    return __check_bit(bm->buffer_long, bit);
}

int bitmap_check_all_set(struct bitmap *bm, long beg, long end)
{
    if (beg > end || end >= bitmap_length(bm) || beg < 0) {
        return 0;
    }
    long first_block = beg >> 3;
    long last_block = end >> 3;
    long first_block_bit = beg & 7;
    long last_block_bit = end & 7;
    unsigned char mask = 0xff;

    /// 如果范围只涉及到一个字节
    if (first_block == last_block) {
        mask <<= first_block_bit;
        mask &= ~(0xff << (last_block_bit + 1));
        return (bm->buffer[first_block] & mask) == mask;
    }

    /// 检查左边界。
    if (first_block_bit != 0) {
        mask <<= first_block_bit;
        if ((bm->buffer[first_block] & mask) != mask) {
            return 0;
        }
        first_block++;
    }
    /// 检查中间完整的block
    while (first_block < last_block) {
        if (bm->buffer[first_block] != 0xff) {
            return 0;
        }
        first_block++;
    }
    /// 检查右边界。
    mask = ~(0xfe << last_block_bit);
    if ((bm->buffer[last_block] & mask) != mask) {
        return 0;
    }

    return !0;
}

int bitmap_check_any_set(struct bitmap *bm, long beg, long end)
{
    if (beg > end || end >= bitmap_length(bm) || beg < 0) {
        return 0;
    }
    long first_block = beg >> 3;
    long last_block = end >> 3;
    long first_block_bit = beg & 7;
    long last_block_bit = end & 7;
    unsigned char mask = 0xff;

    /// 如果范围只涉及到一个字节
    if (first_block == last_block) {
        mask <<= first_block_bit;
        mask &= ~(0xff << (last_block_bit + 1));
        return !!(bm->buffer[first_block] & mask);
    }

    /// 检查左边界。
    if (first_block_bit != 0) {
        mask <<= first_block_bit;
        if ((bm->buffer[first_block] & mask) != 0) {
            return !0;
        }
        first_block++;
    }
    /// 检查中间完整的block
    while (first_block < last_block) {
        if (bm->buffer[first_block] != 0) {
            return !0;
        }
        first_block++;
    }
    /// 检查右边界。
    mask = ~(0xfe << last_block_bit);
    if ((bm->buffer[last_block] & mask) != 0) {
        return !0;
    }

    return 0;
}

long bitmap_first_set_bit_from(struct bitmap *bm, long bit)
{
    long total_length = bitmap_length(bm);
    if (bit >= total_length || bit < 0) {
        return -1;
    }

    long index = bit >> 3;
    long offset = bit & 7;
    unsigned char *buffer = (unsigned char*)(bm->buffer);

    /// 第一个字节区别对待
    if (offset != 0) {
        unsigned char head_bit = buffer[index];
        head_bit &= (unsigned char)(0xff << offset);
        offset = get_byte_first_set_bit[head_bit];
        if (offset < 8) {
            return (index << 3) + offset;
        }
        index++;
        offset = 0;
    }

    /// 在后面的字节中查找
    while (index < bm->map_size) {
        offset = get_byte_first_set_bit[buffer[index]];
        if (offset < 8) {
            return (index << 3) + offset;
        }
        index++;
    }

    return total_length;
}

long bitmap_first_unset_bit_from(struct bitmap *bm, long bit)
{
    long total_length = bitmap_length(bm);
    if (bit >= total_length || bit < 0) {
        return -1;
    }

    long index = bit >> 3;
    long offset = bit & 7;
    unsigned char *buffer = (unsigned char*)(bm->buffer);

    /// 第一个字节区别对待
    if (offset != 0) {
        unsigned char head_bit = ~(buffer[index]);
        head_bit &= (unsigned char)(0xff << offset);
        offset = get_byte_first_set_bit[head_bit];
        if (offset < 8) {
            return (index << 3) + offset;
        }
        index++;
        offset = 0;
    }

    /// 在后面的字节中查找
    while (index < bm->map_size) {
        offset = get_byte_first_set_bit[(unsigned char)(~(buffer[index]))];
        if (offset < 8) {
            return (index << 3) + offset;
        }
        index++;
    }

    return total_length;
}

long bitmap_sizeof_set_block(struct bitmap *bm, long bit)
{
    long next_bit = bitmap_first_unset_bit_from(bm, bit);
    if (next_bit > bit && bit >= 0) {
        return next_bit - bit;
    }
    return -1;
}

long bitmap_sizeof_unset_block(struct bitmap *bm, long bit)
{
    long next_bit = bitmap_first_set_bit_from(bm, bit);
    if (next_bit > bit && bit >= 0) {
        return next_bit - bit;
    }
    return -1;
}

long bitmap_next_set_block(struct bitmap *bm, long bit)
{
    long total_length = bitmap_length(bm);
    long next_bit = bitmap_first_unset_bit_from(bm, bit);
    if (next_bit >= total_length || next_bit < 0) {
        return -1;
    }
    next_bit = bitmap_first_set_bit_from(bm, next_bit);
    if (next_bit >= total_length || next_bit < 0) {
        return -1;
    }
    return next_bit;
}

long bitmap_next_unset_block(struct bitmap *bm, long bit)
{
    long total_length = bitmap_length(bm);
    long next_bit = bitmap_first_set_bit_from(bm, bit);
    if (next_bit >= total_length) {
        return -1;
    }
    next_bit = bitmap_first_unset_bit_from(bm, next_bit);
    if (next_bit >= total_length) {
        return -1;
    }
    return next_bit;
}

int bitmap_set_bit(struct bitmap *bm, long bit)
{
    if (bit >= bitmap_length(bm) || bit < 0) {
        return 0;
    }
    return __set_bit(bm->buffer_long, bit);
}

int bitmap_clear_bit(struct bitmap *bm, long bit)
{
    if (bit >= bitmap_length(bm) || bit < 0) {
        return 1;
    }
    return __clear_bit(bm->buffer_long, bit);
}

void bitmap_set_block(struct bitmap *bm, long beg, long end)
{
    if (beg > end || end >= bitmap_length(bm) || beg < 0) {
        return;
    }
    long first_block = beg >> 3;
    long last_block = end >> 3;
    long first_block_bit = beg & 7;
    long last_block_bit = end & 7;
    unsigned char mask = 0xff;

    /// 如果范围只涉及到一个字节
    if (first_block == last_block) {
        mask <<= first_block_bit;
        mask &= ~(0xff << (last_block_bit + 1));
        bm->buffer[first_block] |= mask;
        return;
    }

    /// 置位左边界。
    if (first_block_bit != 0) {
        mask <<= first_block_bit;
        bm->buffer[first_block] |= mask;
        first_block++;
    }
    /// 置位中间完整的block
    if (first_block < last_block) {
        memset(bm->buffer + first_block, 0xff, last_block - first_block);
    }
    /// 置位右边界。
    mask = ~(0xfe << last_block_bit);
    bm->buffer[last_block] |= mask;
}

void bitmap_clear_block(struct bitmap *bm, long beg, long end)
{
    if (beg > end || end >= bitmap_length(bm) || beg < 0) {
        return;
    }
    long first_block = beg >> 3;
    long last_block = end >> 3;
    long first_block_bit = beg & 7;
    long last_block_bit = end & 7;
    unsigned char mask = 0xff;

    /// 如果范围只涉及到一个字节
    if (first_block == last_block) {
        mask <<= first_block_bit;
        mask &= ~(0xff << (last_block_bit + 1));
        bm->buffer[first_block] &= ~mask;
        return;
    }

    /// 清除左边界。
    if (first_block_bit != 0) {
        mask <<= first_block_bit;
        bm->buffer[first_block] &= ~mask;
        first_block++;
    }
    /// 清除中间完整的block
    if (first_block < last_block) {
        memset(bm->buffer + first_block, 0, last_block - first_block);
    }
    /// 清除右边界。
    mask = 0xfe << last_block_bit;
    bm->buffer[last_block] &= mask;
}
